Bandwidth is a limited commodity in computer data networks. Sharing bandwidth in a computer data network allows multiple user-flows to be present on a data channel at the same time. Variable and fixed amounts of bandwidth can be allotted to particular users and groups of users according to their subscription levels or priorities.
Rate limiting is a process for limiting the amount of bandwidth that network traffic flows can consume. Rate limiting may be implemented for individual network traffic flows or for groups of network traffic flows. Network traffic flows that exceed their bandwidth limit can be subject to an action which effectively decreases the network traffic flow. For example, rate limiting may control a network traffic flow using a reduction in priority, a change in traffic class or type of service (TOS), or a loss of flow packets (i.e., by dropping packets). The dropped packets will routinely be detected by the destination node as not having been received and requested to be retransmitted by the source node.
Conventional rate limiting implementations determine whether or not a network flow is in violation of a configured rate through the use of either timestamps or credit buckets. In timestamp implementations, the time between arriving packets is monitored, and a violation is detected if the time between arriving packets is below a threshold (e.g., a threshold based on the packet size and the transmission rate). In credit bucket implementations, credits for individual or group network flows accumulate over time (e.g., according to a refresh rate), and packets arriving in the corresponding individual or group network flows cause a debit from the credit amount, for example, based on the size of each arriving packet. A violation is detected if the arriving packet debits the credit bucket more than the amount of credit available at the time. Both the timestamp and credit bucket implementations can accumulate unused time or credits to handle larger packets or bursts interspersed with slower traffic. A maximum value or saturation point for accumulated time or credits limits the maximum packet size or impact of a burst of packets.
Conventional rate limiting implementations also include hierarchical rate limiting. Hierarchical rate limiting uses multiple credit buckets (or timers, alternatively) to control network traffic flow. Violation checks for each credit bucket (or timer) are done in parallel and the results are combined. For convenience, hierarchical rate limiting will be discussed in terms of credit buckets, although other implementations use timestamps in a similar manner.
There are different types of hierarchical rate limiting implementations, including using a shared credit bucket for a group of network flows, using a combination of individual and shared credit buckets for a group of individual network flows, and using different credit buckets for a single network flow. Using a shared credit bucket for a group of network flows allows each network flow to use as much as the entire shared credit bucket (e.g., 100 Mbps), but a violation occurs if the total of the combined network flows surpasses the available credit of the shared credit bucket. Using a combination of individual and shared credit buckets is similar, except that the individual network flows may be limited to a lower credit maximum (e.g., 50 Mbps) than the shared credit bucket. Using different credit buckets for a single network flow is implemented by using one credit bucket if the network flow is in a first bandwidth range (e.g., below 50 Mbps) and a different credit bucket if the network flow is in a second bandwidth range (e.g., between 50 Mbps and 100 Mbps). Different rate limiting actions such as priority reduction and packet dropping may be implemented depending on which bucket applies to the network flow.
The control over how bandwidth is partitioned in conventional hierarchical rate limiting implementations is very limited. If a single network flow is allowed to consume all of the bandwidth allocated to a group of network flows, using a shared credit bucket, then all but one of the network flows are precluded from using the shared bandwidth. Alternatively, if multiple, but less than all, network flows are allowed to consume all of the bandwidth, then the remaining network flows are precluded from using the shared bandwidth. Other conventional implementations partition available bandwidth according to straight priority, which also potentially precludes one or more network flows from accessing the shared bandwidth.